#include <iostream>
#include <vector>

void MergeSort(std::vector<int> &arr, int left, int right)
{
	if (left >= right) return;
	//int mid = left + (right - left) / 2;
	int mid = (left + right) >> 1;
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);

	std::vector<int> tmp(right - left + 1);
	int cur1 = left, cur2 = mid + 1, i = 0;
	while(cur1 <= mid && cur2 <= right)
	{
		if (arr[cur1] < arr[cur2])
			tmp[i++] = arr[cur1++];
		else
			tmp[i++] = arr[cur2++];
	}
	while (cur1 <= mid) tmp[i++] = arr[cur1++];
	while(cur2 <= right) tmp[i++] = arr[cur2++];

	for (int i = left; i <= right; i++)
		arr[i] = tmp[i - left];
}

int main()
{
	std::vector<int> arr = { 1, 2 ,45 ,323 ,43, 56, 56, 454 };
	MergeSort(arr, 0, arr.size() - 1);
	for (auto x : arr)
		std::cout << x << " ";
	return 0;
}



//class Solution {
//public:
//    vector<Interval> merge(vector<Interval>& intervals) {
//        sort(intervals.begin(), intervals.end(), [](Interval x, Interval y) {
//            if (x.start < y.start) return true;
//            else if (x.start == y.start && x.end < y.end) return true;
//            else return false;
//            });
//
//        vector<Interval> ret;
//        for (int left = 0, right = 0, n = intervals.size(); right < n; right++)
//        {
//            int l = intervals[right].start, r = intervals[right].end;
//            while (right + 1 < n && intervals[right + 1].start <= r)
//            {
//                right++;
//                l = min(l, intervals[right].start);
//                r = max(r, intervals[right].end);
//            }
//            ret.push_back({ l, r });
//            left = right + 1;
//        }
//        return ret;
//    }
//};